/**
 * @Author Fizz Pu
 * @Date 2020/8/20 下午4:50
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.Arrays;

/**
 * 珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
 * <p>
 * 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。
 * <p>
 * 如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  
 * <p>
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 */
public class Leet875 {
    public static void main(String[] args) {
        Leet875 leet875 = new Leet875();
        leet875.minEatingSpeed(new int[]{3,6,7,11}, 8);
    }

    public int minEatingSpeed(int[] piles, int H) {
        // 从一开始迭代，直到找出最小速度
        // woc 内存超限
        int speed;
        int MaxValue = Integer.MIN_VALUE;
        for(int each : piles){
            MaxValue = Math.max(MaxValue, each);
        }
        int low = 1, high = MaxValue, mid;
        /*
        for(int i = 1; i < MaxValue; ++i){
            if (eatUp(H, i, piles)){
                System.out.println(i);
                return i;
            }
        }
        return -1;
         */

        while (low < high){
            // mid = (low + high) / 2;
            mid = low + ( (high - low) >> 2 ); // 防止high + low 溢出
            if (eatUp(H, mid, piles)){
                high = mid;
            }else {
                low = mid + 1;
            }
        }
        System.out.println(low);
        return high;
    }

    public boolean eatUp(int H, int speed, int[] piles) {
        // 求一个总和
        /*if (piles == null || piles.length == 0) return false;
        // H个小时，每个小时吃speed个,是否可以吃完
        int curHeadIndex = 0;                      // 当前堆下标
        int curHeapRest = piles[curHeadIndex];    // 当前堆剩余个数
        int length = piles.length;
        for (int i = 0; i < H; ++i) {
            if(curHeadIndex >= length) break;
            if (speed >= curHeapRest) {
                ++curHeadIndex;
                if(curHeadIndex>= length)break;
                curHeapRest = piles[curHeadIndex];
            }
            else curHeapRest -= speed;
        }
        return length <= curHeadIndex;*/
        // 比较小时
        int sum = 0; // 吃完要多少个小时
        for (int pile : piles) {
            sum += Math.ceil(pile * 1.0 / speed);
            }
            return sum <= H;
        }
}
